package com.duoduo.树;

import com.duoduo.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 验证二叉搜索树98
 * @author: chaidl  ！
 * @create: 2022-05-18 23:31
 */
public class 验证二叉搜索树98 {
    //使用递归
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode root, long minValue, long maxValue) {
        //要么根节点就为Null，要么就是递归到了叶子结点
        if (root == null) {
            return true;
        }
        if (root.val >= maxValue || root.val <= minValue) {
            return false;
        }
        return isValidBST(root.left, minValue, root.val) && isValidBST(root.right, root.val, maxValue);
    }

    /*基于中序遍历的栈实现*/
    public boolean isValidBSTInOrderWithStack(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        /*用来存储前一个节点的值*/
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            /*如果当前节点的值不大于前一个节点的值，不符合二叉搜索树定义*/
            if (pre != null && root.val <= pre.val) {
                return false;
            }
            pre = root;
            root = root.right;
        }
        return true;
    }

    TreeNode pre = null;

    /*基于中序遍历的递归实现*/
    public boolean isValidBSTInOrder(TreeNode root) {
        if (root == null) {
            return true;
        }
		// 找到最左边的数字
		boolean left = isValidBSTInOrder(root.left);
		if (!left) {
			return false;
		}
        /*这里用于判断是不是找到最左边的节点了，如果是就不用比较*/
        if (pre == null) {
            pre = root;
        }
        /*如果不是就比较这个节点和前一个节点的值*/
        else if (root.val <= pre.val) {
            return false;
        }
        pre = root;
        return isValidBSTInOrder(root.right);
    }

	public static void main(String[] args) {
		TreeNode node=new TreeNode(2);
		node.left = new TreeNode(1);
		node.right = new TreeNode(3);
		boolean validBSTInOrder = new 验证二叉搜索树98().isValidBSTInOrder(node);
		System.out.println(validBSTInOrder);

	}
}
